//https://leetcode.cn/problems/minimum-height-trees/description/?envType=daily-question&envId=2024-03-17


class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        unordered_map<int, unordered_set<int>> mp;
        for (const auto &item: edges){
            mp[item[0]].insert(item[1]);
            mp[item[1]].insert(item[0]);
        }
        vector<int> vec, ret;
        for (const auto &item: mp)
            if (item.second.size() == 1)
                vec.emplace_back(item.first);
        while (mp.size() > 2){
            vector<int> tmp;
            for (const auto &dn: vec){
                for (const auto &cn: mp[dn]){
                    mp[cn].erase(dn);
                    if (mp[cn].size() == 1)
                        tmp.emplace_back(cn);
                }
                mp.erase(dn);
            }
            vec = std::move(tmp);
        }
        for (const auto &item: mp)
            ret.emplace_back(item.first);
        return ret;
    }
};